#!/usr/bin/env python
import sys
import heapq

def makeHuffTree(symbolTupleList):
    trees = list(symbolTupleList)
    heapq.heapify(trees)
    while len(trees) > 1:
        childR, childL = heapq.heappop(trees), heapq.heappop(trees)
        parent = (childL[0] + childR[0], childL, childR)
        heapq.heappush(trees, parent)
    return trees[0]

def printHuffTree(huffTree, prefix = ''):
    if len(huffTree) == 2:
        print huffTree[1], prefix

    else:
        printHuffTree(huffTree[1], prefix + '0')
        printHuffTree(huffTree[2], prefix + '1')


def getHuffCode(huffTree, code, prefix = ''):
    if len(huffTree) == 2:
        code[huffTree[1]]=prefix
    else:
        getHuffCode(huffTree[1], code, prefix + '0')
        getHuffCode(huffTree[2], code, prefix + '1')

if __name__ == '__main__':
    exampleData = [
      (0.124167  , 'e'),   
      (0.0969225 , 't'),   
      (0.0820011 , 'a'),   
      (0.0768052 , 'i'),   
      (0.0764055 , 'n'),   
      (0.0714095 , 'o'),   
      (0.0706768 , 's'),   
      (0.0668132 , 'r'),   
      (0.0448308 , 'l'),   
      (0.0363709 , 'd'),   
      (0.0350386 , 'h'),   
    ]

    huffTree = makeHuffTree(exampleData)
    #printHuffTree(huffTree)
    code = {}
    getHuffCode(huffTree, code)
    print code


